package com.yanceysong.codetop.s21_s30;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class S24_Mid_54_螺旋矩阵 {

    /**
     * 螺旋矩阵 (Spiral Matrix) - LeetCode 54
     * 题目要求：给定一个 m 行 n 列的矩阵 matrix，按 顺时针螺旋 顺序返回矩阵中所有元素。
     * 链接：<a href="https://leetcode.cn/problems/spiral-matrix/">...</a>
     * <p>
     * 示例1：
     * 输入：
     * .[
     * .  [1, 2, 3],
     * .  [4, 5, 6],
     * .  [7, 8, 9]
     * .]
     * 输出： [1, 2, 3, 6, 9, 8, 7, 4, 5]
     * <p>
     * 示例2：
     * 输入：
     * .[
     * .  [1, 2, 3, 4],
     * .  [5, 6, 7, 8],
     * .  [9,10,11,12]
     * .]
     * 输出： [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
     * <p>
     * 思路解析（边界收缩法 / 层序剥洋葱）：
     * 我们维护四个边界指针：
     * top    —— 当前还未被遍历的最上面一行的索引（初始为 0）
     * bottom —— 当前还未被遍历的最下面一行的索引（初始为 m-1）
     * left   —— 当前还未被遍历的最左侧一列的索引（初始为 0）
     * right  —— 当前还未被遍历的最右侧一列的索引（初始为 n-1）
     * <p>
     * 每一轮遍历按以下顺序执行（如果对应的行/列仍有效）：
     * 1. 从左到右  遍历 top 行，然后 top++ （这一行已经处理完毕）
     * 2. 从上到下  遍历 right 列，然后 right--（这一列已经处理完毕）
     * 3. 从右到左  遍历 bottom 行，然后 bottom--（注意：需要确保 top <= bottom）
     * 4. 从下到上  遍历 left 列，然后 left++ （注意：需要确保 left <= right）
     * <p>
     * ASCII 示意（以 4x5 为例）：
     * 第一层：
     * . (top,left) → → → → (top,right)
     * .      ↓             ↓
     * .      ↓             ↓
     * .  (bottom,left) ← ← (bottom,right)
     * 然后边界收缩，继续处理内圈。
     * <p>
     * 循环终止条件： 当 left > right 或者 top > bottom 时，说明所有层都遍历完成。
     * <p>
     * 复杂度分析：
     * 时间复杂度：O(m * n) —— 每个元素访问一次。
     * 空间复杂度：O(1)（结果列表除外）—— 只使用了常数额外变量。
     * <p>
     * 注意点 / 易错点：
     * - 不是正方形时（m != n），依旧适用该逻辑。
     * - 需要在第三步 & 第四步前做边界检查，避免重复遍历同一行或同一列。
     * - 如果使用固定数组 + Arrays.asList 返回，会得到不可变长度的列表；这里直接用 ArrayList 收集结果。
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        // 容错：空矩阵或行数为0
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new ArrayList<>();
        }

        int rows = matrix.length;          // 总行数 m
        int cols = matrix[0].length;       // 总列数 n

        // 四个边界指针（动态收缩）
        int top = 0;               // 当前未遍历的最上面一行
        int bottom = rows - 1;     // 当前未遍历的最下面一行
        int left = 0;              // 当前未遍历的最左边一列
        int right = cols - 1;      // 当前未遍历的最右边一列

        List<Integer> result = new ArrayList<>(rows * cols); // 预分配容量，避免扩容

        while (left <= right && top <= bottom) {
            // 1) 从左到右：遍历当前 top 行
            for (int col = left; col <= right; col++) {
                result.add(matrix[top][col]);
            }
            top++; // 收缩上边界

            // 2) 从上到下：遍历当前 right 列
            for (int row = top; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            right--; // 收缩右边界

            // 重要：在遍历下边之前检查是否还有有效的行
            if (top <= bottom) {
                // 3) 从右到左：遍历当前 bottom 行
                for (int col = right; col >= left; col--) {
                    result.add(matrix[bottom][col]);
                }
                bottom--; // 收缩下边界
            }

            // 重要：在遍历左边之前检查是否还有有效的列
            if (left <= right) {
                // 4) 从下到上：遍历当前 left 列
                for (int row = bottom; row >= top; row--) {
                    result.add(matrix[row][left]);
                }
                left++; // 收缩左边界
            }
        }
        return result;
    }
    // ============================= 测试代码区域 =============================

    public static void main(String[] args) {
        S24_Mid_54_螺旋矩阵 solution = new S24_Mid_54_螺旋矩阵();
        System.out.println("=== 螺旋矩阵 测试开始 ===\n");

        testSquare3x3(solution);          // 测试1：正方形 3x3
        testRectangleMoreCols(solution);  // 测试2：列多 3x4
        testRectangleMoreRows(solution);  // 测试3：行多 4x3
        testSingleRow(solution);          // 测试4：单行
        testSingleColumn(solution);       // 测试5：单列
        testSingleElement(solution);      // 测试6：单元素
        testLeetCodeExample2(solution);   // 测试7：官方示例2 (3x4)
        testNonSquareEdge(solution);      // 测试8：更复杂 5x4

        System.out.println("\n=== 所有测试完成 ===");
    }

    // -------------------------- 单个测试方法 --------------------------

    private static void testSquare3x3(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试1] 正方形 3x3");
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(1, 2, 3, 6, 9, 8, 7, 4, 5);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试1失败";
        System.out.println();
    }

    private static void testRectangleMoreCols(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试2] 矩形 行<列 3x4");
        int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试2失败";
        System.out.println();
    }

    private static void testRectangleMoreRows(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试3] 矩形 行>列 4x3");
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9},
                {10, 11, 12}
        };
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(1, 2, 3, 6, 9, 12, 11, 10, 7, 4, 5, 8);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试3失败";
        System.out.println();
    }

    private static void testSingleRow(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试4] 单行 1x5");
        int[][] matrix = {
                {1, 2, 3, 4, 5}
        };
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(1, 2, 3, 4, 5);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试4失败";
        System.out.println();
    }

    private static void testSingleColumn(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试5] 单列 5x1");
        int[][] matrix = {
                {1},
                {2},
                {3},
                {4},
                {5}
        };
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(1, 2, 3, 4, 5);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试5失败";
        System.out.println();
    }

    private static void testSingleElement(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试6] 单元素 1x1");
        int[][] matrix = {{42}};
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(42);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试6失败";
        System.out.println();
    }

    private static void testLeetCodeExample2(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试7] 官方示例2 3x4");
        int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试7失败";
        System.out.println();
    }

    private static void testNonSquareEdge(S24_Mid_54_螺旋矩阵 solution) {
        System.out.println("[测试8] 较复杂矩形 5x4");
        int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16},
                {17, 18, 19, 20}
        };
        List<Integer> res = solution.spiralOrder(matrix);
        List<Integer> expected = Arrays.asList(1, 2, 3, 4, 8, 12, 16, 20, 19, 18, 17, 13, 9, 5, 6, 7, 11, 15, 14, 10);
        printMatrix(matrix);
        printResult(res, expected);
        assert res.equals(expected) : "测试8失败";
        System.out.println();
    }

    // -------------------------- 工具方法 --------------------------

    private static void printMatrix(int[][] matrix) {
        System.out.println("输入矩阵：");
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }

    private static void printResult(List<Integer> actual, List<Integer> expected) {
        System.out.println("螺旋输出  : " + actual);
        System.out.println("期望结果  : " + expected);
        System.out.println(actual.equals(expected) ? "结果: ✓ 正确" : "结果: ✗ 错误");
    }
}
